{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #长度最小的子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #prefix-sum #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #前缀和 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSubArrayLen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #长度最小的子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个含有&nbsp;<code>n</code><strong>&nbsp;</strong>个正整数的数组和一个正整数 <code>target</code><strong> 。</strong></p>\n",
    "\n",
    "<p>找出该数组中满足其和<strong> </strong><code>&ge; target</code><strong> </strong>的长度最小的 <strong>连续子数组</strong>&nbsp;<code>[nums<sub>l</sub>, nums<sub>l+1</sub>, ..., nums<sub>r-1</sub>, nums<sub>r</sub>]</code> ，并返回其长度<strong>。</strong>如果不存在符合条件的子数组，返回 <code>0</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = 7, nums = [2,3,1,2,4,3]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>子数组&nbsp;<code>[4,3]</code>&nbsp;是该条件下的长度最小的子数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = 4, nums = [1,4,4]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = 11, nums = [1,1,1,1,1,1,1,1]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>提示：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= target &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>进阶：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果你已经实现<em> </em><code>O(n)</code> 时间复杂度的解法, 请尝试设计一个 <code>O(n log(n))</code> 时间复杂度的解法。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 209&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/minimum-size-subarray-sum/\">https://leetcode-cn.com/problems/minimum-size-subarray-sum/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [2VG8Kg](https://leetcode.cn/problems/2VG8Kg/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [2VG8Kg](https://leetcode.cn/problems/2VG8Kg/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7\\n[2,3,1,2,4,3]', '4\\n[1,4,4]', '11\\n[1,1,1,1,1,1,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return 0\n",
    "        left = 0\n",
    "        re = math.pow(10, 5)\n",
    "        wim = 0\n",
    "\n",
    "        for right, x in enumerate(nums):\n",
    "            wim = wim + x\n",
    "            while wim>=target:\n",
    "                re = min(re,right-left+1)\n",
    "                wim =wim-nums[left]\n",
    "                left=left+1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "\n",
    "        left=total=0\n",
    "\n",
    "        ret=float(\"inf\")\n",
    "\n",
    "        for right,num in enumerate(nums):\n",
    "            total+=num\n",
    "            while total>=target:\n",
    "\n",
    "                ret=min(ret,right-left+1)\n",
    "                total-=nums[left]\n",
    "                left+=1\n",
    "        return 0 if ret >len(nums)  else ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s: int, nums: List[int]) -> int:        \n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        n = len(nums)\n",
    "        ans = n + 1\n",
    "        sums = [0]\n",
    "        for i in range(n):\n",
    "            sums.append(sums[-1] + nums[i])\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            target = s + sums[i - 1]\n",
    "            bound = bisect.bisect_left(sums, target)\n",
    "            if bound != len(sums):\n",
    "                ans = min(ans, bound - (i - 1))\n",
    "        \n",
    "        return 0 if ans == n + 1 else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        start = end = sum0 = 0\n",
    "        min_len = inf\n",
    "        while end < len(nums):\n",
    "            sum0 += nums[end]\n",
    "            while start >= 0 and sum0 >= target:\n",
    "                min_len = min(min_len,end - start + 1)\n",
    "                sum0 -= nums[start]\n",
    "                start += 1 \n",
    "            end += 1\n",
    "        return min_len if min_len != inf else 0\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        # 数组：快慢双指针\n",
    "        ret = float('inf')\n",
    "        slow, fast, sums = 0, 0, 0\n",
    "        while fast < len(nums):\n",
    "            sums += nums[fast]\n",
    "            while sums >= target:\n",
    "                ret = min(ret, fast - slow + 1)\n",
    "                sums -= nums[slow]\n",
    "                slow += 1\n",
    "            fast += 1\n",
    "        return ret if ret != float('inf') else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        l, r = 0, 1\n",
    "        n = len(nums)\n",
    "        start = 0\n",
    "        end = n\n",
    "        while l <= r and r <= n:\n",
    "            su = sum(nums[l:r])\n",
    "            if su < target:\n",
    "                r += 1\n",
    "            elif su >= target:\n",
    "                if (end - start) > (r - l):\n",
    "                    start, end = l, r\n",
    "                l += 1\n",
    "        print(start,end)\n",
    "        if (end - start) == n and sum(nums) < target:\n",
    "            return 0\n",
    "        return end - start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        \n",
    "\n",
    "        n = len(nums)\n",
    "        ans = n+1\n",
    "        sum =0\n",
    "        left = 0 \n",
    "        for right ,x in enumerate(nums):\n",
    "            sum += x\n",
    "            while sum - nums[left] >=target:\n",
    "                sum -=nums[left]\n",
    "                left+=1\n",
    "            if sum >= target:\n",
    "                ans = min(ans,right-left+1)\n",
    "        return ans if ans<=n else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        if sum(nums)<target:\n",
    "            return 0\n",
    "        re = math.pow(10, 5)\n",
    "        temp = []\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            temp.append(nums[i])\n",
    "            while sum(temp)>=target:\n",
    "                re = min(re, len(temp))\n",
    "                temp.pop(0)\n",
    "\n",
    "\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        s = 0\n",
    "        ans = inf\n",
    "        left = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            s+=num\n",
    "            while s >= target:\n",
    "                ans = min(ans, right-left+1)\n",
    "                s -= nums[left]\n",
    "                left += 1\n",
    "                \n",
    "        return ans if ans!=inf else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        min_len = float('inf')\n",
    "\n",
    "        l, r = 0, 0\n",
    "\n",
    "        _sum = 0\n",
    "\n",
    "        while r < n:\n",
    "            _sum += nums[r]\n",
    "\n",
    "            while _sum >= target:\n",
    "                min_len = min(min_len, r - l + 1)\n",
    "                _sum -= nums[l]\n",
    "                l += 1\n",
    "            r +=1\n",
    "        return 0 if min_len == float('inf') else min_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        if sum(nums)<target:\n",
    "            return 0\n",
    "        if target in nums:\n",
    "            return 1\n",
    "        slow,fast=0,0\n",
    "        min_=float('inf')\n",
    "        result=0\n",
    "        while fast<len(nums):\n",
    "            result+=nums[fast]\n",
    "            while result>=target:\n",
    "                min_=min(min_,fast-slow+1)\n",
    "                result-=nums[slow]\n",
    "                slow+=1\n",
    "            fast+=1\n",
    "        return min_\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        start = end = sum0 = 0\n",
    "        min_len = float(\"inf\")\n",
    "        while end < len(nums):\n",
    "            sum0 += nums[end]\n",
    "            while start >= 0 and sum0 >= target:\n",
    "                min_len = min(min_len,end - start + 1)\n",
    "                sum0 -= nums[start]\n",
    "                start += 1 \n",
    "            end += 1\n",
    "        return min_len if min_len != inf else 0\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        start,end=0,0\n",
    "        sumval=0\n",
    "        ans=len(nums)+1\n",
    "        while end<len(nums):\n",
    "            sumval+=nums[end]\n",
    "            while sumval>=target:\n",
    "                ans=min(ans,end-start+1)\n",
    "                sumval-=nums[start]\n",
    "                start+=1\n",
    "            end+=1\n",
    "        if ans==len(nums)+1:\n",
    "            return 0\n",
    "        else:\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        l, r = 0, 0\n",
    "        n = len(nums)\n",
    "        s = 0\n",
    "        res = float(\"inf\")\n",
    "        while r < n:\n",
    "            s += nums[r]\n",
    "            \n",
    "            while s >= target:\n",
    "                res = min(res, r - l + 1)\n",
    "                s -= nums[l] \n",
    "                l += 1\n",
    "            r += 1\n",
    "        return res if res != float(\"inf\") else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = n + 1\n",
    "        s = left = 0\n",
    "        for right, x in enumerate(nums):\n",
    "            s += x\n",
    "            while s >= target:\n",
    "                ans = min(ans, right - left + 1)\n",
    "                s -= nums[left]\n",
    "                left += 1\n",
    "\n",
    "        return ans if ans <= n else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        start,end=0,0\n",
    "        n=len(nums)\n",
    "        total=0\n",
    "        ans=n+1\n",
    "        while end<n:\n",
    "            total+=nums[end]\n",
    "            while total>=target:\n",
    "                ans= min (ans,end-start+1)\n",
    "                total-=nums[start]\n",
    "                start+=1\n",
    "            end+=1\n",
    "        return 0 if ans==n+1 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        res = float(\"inf\")\n",
    "\n",
    "\n",
    "        l, r = 0, 0\n",
    "        curSum = 0\n",
    "        while r < n:\n",
    "\n",
    "            while r < n and curSum < target:\n",
    "                curSum += nums[r]\n",
    "                r += 1\n",
    "            \n",
    "            if r == n and curSum < target:\n",
    "                break\n",
    "\n",
    "            while curSum >= target:\n",
    "                curSum -= nums[l]\n",
    "                l += 1\n",
    "\n",
    "            res = min(res, r  - l  + 1)\n",
    "\n",
    "        return res if res != float(\"inf\") else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        fast, slow, n = 0, 0, len(nums)\n",
    "        tmpsum, ret = 0, n + 1\n",
    "\n",
    "        while fast < n:\n",
    "            tmpsum += nums[fast]\n",
    "            while tmpsum >= target:\n",
    "                ret = min(ret, fast - slow + 1)\n",
    "                tmpsum -= nums[slow]\n",
    "                slow += 1\n",
    "            fast += 1\n",
    "            \n",
    "        return 0 if ret ==  n + 1 else ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = n + 1\n",
    "        left = 0\n",
    "        cnt = 0\n",
    "        for right, x in enumerate(nums):\n",
    "            cnt += x\n",
    "            while cnt >= target:\n",
    "                res = min(res, right - left + 1)\n",
    "                cnt -= nums[left]\n",
    "                left += 1\n",
    "        return res if res <= n else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        sum_tmp = nums[0]\n",
    "        rs = 10**6 if nums[0]<target else 1\n",
    "        nums_l = len(nums)\n",
    "\n",
    "        # 滑动窗口，先找到满足条件的，然后尽量缩小窗口；不断右移窗口\n",
    "        l, r = 0, 1  # 窗口左右边界\n",
    "        while r<nums_l:\n",
    "            sum_tmp += nums[r]\n",
    "\n",
    "            while sum_tmp>=target:  # 满足条件，缩窗口，找到到当前位置满足条件的最小长度\n",
    "                rs = min(rs, r-l+1)\n",
    "                sum_tmp -= nums[l]\n",
    "                l += 1\n",
    "            \n",
    "            r += 1\n",
    "\n",
    "\n",
    "        return rs if rs<10**6 else 0\n",
    "                    \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        n = len(nums)\n",
    "        ans = n+1\n",
    "        start , end = 0,0\n",
    "        total = 0\n",
    "        while end < n:\n",
    "            total += nums[end]\n",
    "            while total >= target:\n",
    "                ans = min(ans,end-start+1)\n",
    "                total-=nums[start]\n",
    "                start+=1\n",
    "            end+=1\n",
    "        return 0 if ans == n+1 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 滑窗 时间复杂度O(n)\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        window_sum = 0\n",
    "        n = len(nums)\n",
    "        res = math.inf\n",
    "        l , r = 0, 0\n",
    "        for r in range(n):\n",
    "            window_sum += nums[r]\n",
    "            while window_sum >= target:\n",
    "                res = min(res, r - l + 1)\n",
    "                window_sum -= nums[l]\n",
    "                l += 1\n",
    "        return res if res <= len(nums) else 0\n",
    "\n",
    "    # 前缀和 + 二分 时间复杂度O(n log(n))\n",
    "    # def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "    #     n = len(nums)\n",
    "    #     res = math.inf\n",
    "    #     pre_sum = [0 for _ in range(n + 1)]\n",
    "    #     for i in range(0, n):\n",
    "    #         pre_sum[i + 1] = pre_sum[i] + nums[i]\n",
    "    #     if pre_sum[-1] < target: return 0\n",
    "    #     for i in range(n + 1):\n",
    "    #         l, r = i, n + 1\n",
    "    #         while l < r:\n",
    "    #             mid = l + (r - l) // 2\n",
    "    #             if pre_sum[mid] - pre_sum[i] >= target:\n",
    "    #                 r = mid\n",
    "    #             else:\n",
    "    #                 l = mid + 1\n",
    "    #         if l < n + 1:\n",
    "    #             res = min(res, l - i)\n",
    "    #     return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s: int, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        n = len(nums)\n",
    "        ans = n + 1\n",
    "        start, end = 0, 0\n",
    "        total = 0\n",
    "        while end < n:\n",
    "            total += nums[end]\n",
    "            while total >= s:\n",
    "                ans = min(ans, end - start + 1)\n",
    "                total -= nums[start]\n",
    "                start += 1\n",
    "            end += 1\n",
    "        \n",
    "        return 0 if ans == n + 1 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        left,right = 0,0\n",
    "        curSum = 0\n",
    "        curLen = 0\n",
    "        minLen = len(nums) + 1\n",
    "        while right < len(nums):\n",
    "            curSum += nums[right]\n",
    "            right += 1\n",
    "            curLen += 1\n",
    "            while curSum >= target and left <= right:\n",
    "                if curLen < minLen:\n",
    "                    minLen = curLen\n",
    "                curSum -= nums[left]\n",
    "                curLen -= 1\n",
    "                left += 1\n",
    "        return 0 if minLen == len(nums) + 1 else minLen "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        l = 0 \n",
    "        minLen = len(nums)+1\n",
    "        s = 0\n",
    "        for  r,x in enumerate(nums):\n",
    "            s += x\n",
    "            while s>=target:\n",
    "                minLen = min(minLen,r-l+1)\n",
    "                s -= nums[l]\n",
    "                l += 1\n",
    "        return minLen if minLen<=len(nums) else 0 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        ans = n + 1\n",
    "        start = 0\n",
    "        end = 0\n",
    "        total = 0\n",
    "        while end < n:\n",
    "            total += nums[end]\n",
    "            while total >= target:\n",
    "                ans = min(ans, end - start + 1)\n",
    "                total -= nums[start]\n",
    "                start += 1\n",
    "            end += 1\n",
    "        return 0 if ans == n + 1 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 滑窗 时间复杂度O(n)\n",
    "    # def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "    #     window_sum = 0\n",
    "    #     n = len(nums)\n",
    "    #     res = math.inf\n",
    "    #     l , r = 0, 0\n",
    "    #     while r < n:\n",
    "    #         window_sum += nums[r]\n",
    "    #         while window_sum >= target:\n",
    "    #             res = min(res, r - l + 1)\n",
    "    #             window_sum -= nums[l]\n",
    "    #             l += 1\n",
    "    #         r += 1\n",
    "    #     return res if res <= len(nums) else 0\n",
    "\n",
    "    # 前缀和 + 二分 时间复杂度O(n log(n))\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = math.inf\n",
    "        for i in range(1, n):\n",
    "            nums[i] += nums[i - 1]\n",
    "        nums = [0] + nums\n",
    "        if nums[-1] < target: return 0\n",
    "        for i in range(n):\n",
    "            l, r = i, n\n",
    "            while l < r:\n",
    "                mid = l + (r - l) // 2\n",
    "                if nums[mid + 1] - nums[i] >= target:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if l < n:\n",
    "                res = min(res, l - i + 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        l,r = 0,0\n",
    "        res = float('inf')\n",
    "        ans = 0\n",
    "        while r<len(nums):\n",
    "            ans += nums[r]  \n",
    "            while ans >= target:\n",
    "                res = min(res, r-l+1)\n",
    "                if res == 1: return res\n",
    "                print(l)\n",
    "                ans -= nums[l]\n",
    "                l+=1\n",
    "            # if res == 1:\n",
    "            #     return res\n",
    "            r += 1\n",
    "        return res if res != float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        sum = 0\n",
    "        ans = inf\n",
    "        left = 0\n",
    "        for i in range(len(nums)):\n",
    "            sum += nums[i]\n",
    "            while sum >= target:\n",
    "                sum -= nums[left]\n",
    "                ans = min(ans, i - left + 1)\n",
    "                left += 1\n",
    "            print(i, sum, ans)\n",
    "        return ans if ans != inf else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        if len(nums) <= 0:\n",
    "            return 0\n",
    "        left, right = 0, 0\n",
    "        temp = []\n",
    "        _min = float('inf')\n",
    "        _sum = 0\n",
    "        for right in range(len(nums)):\n",
    "            temp.append(nums[right])\n",
    "            _sum += nums[right]\n",
    "            while _sum >= target:\n",
    "                _min = min(_min, right - left + 1)\n",
    "                _sum -= nums[left]\n",
    "                left += 1\n",
    "                \n",
    "        if _min == float(inf):\n",
    "            _min = 0\n",
    "        return _min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        left, right = 0, 0\n",
    "        current = nums[left]\n",
    "        if current >= target:\n",
    "            return 1\n",
    "        min_size = len(nums) + 1\n",
    "\n",
    "        while right < len(nums) - 1:\n",
    "            while current < target and right < len(nums) - 1:\n",
    "                right += 1\n",
    "                current += nums[right]\n",
    "                print(\"add\", left, right, current)\n",
    "            if current >= target:\n",
    "                min_size = min_size if min_size < right - left + 1 else right - left + 1\n",
    "            while current >= target and left < right:\n",
    "                left += 1\n",
    "                current -= nums[left-1]\n",
    "                print(\"reduce\", left, right, current)\n",
    "                if current >= target:\n",
    "                    min_size = min_size if min_size < right - left + 1 else right - left + 1\n",
    "                if min_size == 1:\n",
    "                    return min_size\n",
    "        return min_size if min_size != len(nums) + 1 else 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        if sum(nums)<target: return 0\n",
    "        left = 0\n",
    "        sum_s = 0\n",
    "        res = 100000\n",
    "        for right in range(len(nums)):\n",
    "            sum_s += nums[right]\n",
    "            print(left,right,sum_s)\n",
    "            while sum_s>= target:\n",
    "                res = min(right-left+1, res)\n",
    "                sum_s -= nums[left]\n",
    "                left += 1\n",
    "        return res     \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        left=0\n",
    "        right=0\n",
    "        min_len=inf\n",
    "        nums_sum=0\n",
    "\n",
    "        while right < len(nums):\n",
    "            print(right,left,nums_sum,min_len)\n",
    "            nums_sum += nums[right]\n",
    "\n",
    "            while nums_sum >= target:\n",
    "                min_len=min(right-left+1,min_len)\n",
    "                nums_sum -= nums[left]\n",
    "                left += 1\n",
    "            right += 1\n",
    "        if min_len == inf :return 0\n",
    "        return min_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        left=0\n",
    "        right=0\n",
    "        count=0\n",
    "        min_v=float(\"inf\")\n",
    "        while right<len(nums):\n",
    "            count+=nums[right]\n",
    "            print(left,right,count)\n",
    "\n",
    "            if count>=target:\n",
    "                min_v=min(min_v,right-left+1)\n",
    "                while count>=target:\n",
    "                    min_v=min(min_v,right-left+1)\n",
    "                    count-= nums[left]\n",
    "                    left+=1\n",
    "            right+=1\n",
    "        if min_v==float(\"inf\"):\n",
    "            return 0\n",
    "        return min_v\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        ans = 1e7\n",
    "        left,right = 0,0\n",
    "        while left< len(nums) and right<len(nums):\n",
    "            cur = sum(nums[left:right+1])\n",
    "            print(cur)\n",
    "            if cur < target:\n",
    "                right+=1\n",
    "            else:\n",
    "                ans = min(ans, right-left+1)\n",
    "                left+=1\n",
    "        \n",
    "        return ans if ans < 1e6 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        res = len(nums)+1\n",
    "        sum_tmp = nums[0]\n",
    "        while left < len(nums) and right < len(nums) and left <= right:\n",
    "            print(left)\n",
    "            print(right)\n",
    "            print(sum_tmp)\n",
    "            print(res)\n",
    "            if sum_tmp >= target:\n",
    "                res = min(res,right-left+1)\n",
    "                sum_tmp -= nums[left]\n",
    "                left += 1\n",
    "            if sum_tmp < target:\n",
    "                if right == len(nums)-1:\n",
    "                    res = min(res,len(nums)+1)\n",
    "                    break\n",
    "                else:\n",
    "                    right += 1\n",
    "                    sum_tmp += nums[right]\n",
    "        # print(res)       \n",
    "        if res == len(nums)+1:\n",
    "            res = 0\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        start, end = 0, 0\n",
    "        total = 0\n",
    "        while end < len(nums):\n",
    "            total += nums[end]\n",
    "            while total >= target:\n",
    "                if result == 0:\n",
    "                    result = end - start + 1\n",
    "                else:\n",
    "                    result = min(result, end - start + 1)\n",
    "                print(start, end, total)\n",
    "                print(result)\n",
    "                if result == 1:\n",
    "                    return result\n",
    "                total -= nums[start]\n",
    "                start += 1\n",
    "            end += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        \"\"\"n = len(nums)\n",
    "        i, j = 0, 0\n",
    "        tmp = nums[0]\n",
    "        ans = 2**31-1\n",
    "        while True:\n",
    "            while j < n-1 and tmp < target:\n",
    "                j += 1\n",
    "                tmp += nums[j]\n",
    "            if j == n-1 and tmp < target:\n",
    "                break\n",
    "            ans = min(ans, j-i+1)\n",
    "            while i < j and tmp >= target:\n",
    "                tmp -= nums[i]\n",
    "                i += 1\n",
    "            if tmp < target:\n",
    "                ans = min(ans, j-i+2)\n",
    "            else:\n",
    "                ans = 1\n",
    "                break\n",
    "        return 0 if ans == 2**31-1 else ans\"\"\"\n",
    "        sums = [0]\n",
    "        n = len(nums)\n",
    "        ans = 2**31-1\n",
    "        for i in range(n):\n",
    "            sums.append(nums[i]+sums[-1])\n",
    "        for i in range(1, n+1):\n",
    "            if sums[i] < target:\n",
    "                continue\n",
    "            l, r = 0, i\n",
    "            while l <= r:\n",
    "                m = l + (r-l)//2\n",
    "                if sums[i]-sums[m]>= target and (m==i or sums[i]-sums[m+1]<target):\n",
    "                    l = m\n",
    "                    break\n",
    "                if sums[i]-sums[m]>=target:\n",
    "                    l = m+1\n",
    "                else:\n",
    "                    r = m-1\n",
    "            ans = min(ans, i-l)\n",
    "        return ans if ans <= n else 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        if sum(nums) < target :\n",
    "            return 0\n",
    "        left = 0\n",
    "        right = 0\n",
    "        result =0\n",
    "        count = float('inf')\n",
    "        while  right < len(nums)  :\n",
    "            if result < target :\n",
    "                result += nums[right]\n",
    "                right += 1\n",
    "            else :\n",
    "                count = min(count,right-left)\n",
    "                result -= nums[left]\n",
    "                left += 1\n",
    "            print(left,right,result,count)\n",
    "        while result >= target :\n",
    "            count = min(count,len(nums)-left)\n",
    "            result -= nums[left]\n",
    "            left += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        #初始化变量\n",
    "        len_s = len(nums)\n",
    "        min_len = len_s + 1\n",
    "\n",
    "        start = 0\n",
    "        total = 0\n",
    "\n",
    "        #滑动窗口解法\n",
    "        for end in range(len_s):\n",
    "            total = total + nums[end]\n",
    "\n",
    "            if total >= target:\n",
    "                min_len = min(min_len, end - start + 1)\n",
    "                print(min_len, start, end)\n",
    "\n",
    "            while total >= target:\n",
    "                min_len = min(min_len, end - start + 1)\n",
    "                total = total - nums[start]\n",
    "                start += 1\n",
    "\n",
    "        if min_len > len_s:\n",
    "            min_len = 0\n",
    "\n",
    "        return min_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        import itertools\n",
    "        nums  = [0]+list(itertools.accumulate(nums))\n",
    "        if nums[-1] < target:\n",
    "            return 0\n",
    "        min_len = len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i,len(nums)):\n",
    "                if nums[j]-nums[i]>= target:\n",
    "                    min_len = min(min_len,j-i)\n",
    "                    break\n",
    "        return min_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        dp = [0] + nums\n",
    "        dp1 = [0] + nums\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            for j in range(1, len(nums) + 1):\n",
    "                if dp[j] >= target:\n",
    "                    return i\n",
    "                else:\n",
    "                    dp1[j] = dp[j-1] + nums[j-1]\n",
    "            dp = dp1\n",
    "            dp1 = [0] + nums\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        r=[0]\n",
    "        y=[]\n",
    "        for i in nums:\n",
    "            r.append(r[-1]+i)\n",
    "        n=len(r)\n",
    "        if r[-1]<target:return 0\n",
    "        if target in nums:return 1\n",
    "        \n",
    "        for j in range(n):\n",
    "            a,b=j,n-1\n",
    "            while a<b:\n",
    "                m=(a+b)//2\n",
    "                if r[m]-r[j]<target:\n",
    "                    a=m+1\n",
    "                else:\n",
    "                    b=m\n",
    "            if r[a]-r[j]>=target:\n",
    "                y.append(a-j)\n",
    "        return min(y)\n",
    "                    \n",
    "            \n",
    "                \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        i = j = sum = temp = 0\n",
    "        print(nums, target)\n",
    "        while j<len(nums) or sum >= target:\n",
    "            if sum >= target:\n",
    "               sum -= nums[i]\n",
    "               i += 1\n",
    "            else:\n",
    "                sum += nums[j]\n",
    "                j+=1\n",
    "            if sum >= target and (temp > j - i  or temp == 0):\n",
    "                temp = j - i \n",
    "            print(sum,i,j,temp)\n",
    "        return temp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        if target > sum(nums):\n",
    "            return 0\n",
    "        l1 = nums[:]\n",
    "        ans = 1\n",
    "        n = len(nums)\n",
    "        while ans <= n:\n",
    "            if target <= max(l1):\n",
    "                return ans\n",
    "            l1 = l1[:-1]\n",
    "            for i in range(ans, n):\n",
    "                l1[i - ans] += nums[i]\n",
    "            ans += 1\n",
    "        return 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if sum(nums)<target:\n",
    "            return 0\n",
    "        cur=0\n",
    "        presum=[0]\n",
    "        for i in range(n):\n",
    "            cur+=nums[i]\n",
    "            presum.append(cur)\n",
    "        cmin=1\n",
    "        cmax=n\n",
    "        def check(mid):\n",
    "            e=[presum[i+mid]-presum[i] for i in range(n-mid+1)]\n",
    "            return max(e)>=target\n",
    "        while cmin<=cmax:\n",
    "            mid=(cmin+cmax)//2\n",
    "            if check(mid):\n",
    "                cur=mid\n",
    "                cmax=mid-1\n",
    "            else:\n",
    "                cmin=mid+1\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        '''\n",
    "        l = 0                           # 初始化左边界\n",
    "        n = len(nums)\n",
    "        out = n+1                       # 初始化返回值 out = 最小值 or 最大值\n",
    "        res = 0\n",
    "        for r in range(n):              # for 右边界 in 可迭代对象:\n",
    "            res += nums[r]                  # 更新窗口内部信息\n",
    "            while res >= target:            # while 根据题意进行调整：\n",
    "                out = min(out, r-l+1)           # 比较并更新out(收缩场景时)\n",
    "                res -= nums[l]\n",
    "                l += 1                          # 扩张或收缩窗口大小\n",
    "                                            # 比较并更新out(扩张场景时)，本题为收缩场景\n",
    "        return 0 if out == n+1 else out\n",
    "        '''\n",
    "        n = len(nums)\n",
    "        part_sum = []\n",
    "        for i in range(n):\n",
    "            part_sum.append(sum(nums[:i+1]))\n",
    "        part_sum.insert(0,0)\n",
    "        print(part_sum)\n",
    "        \n",
    "        if part_sum[-1] < target:\n",
    "            return 0\n",
    "        \n",
    "        l = 0\n",
    "        out = n+1\n",
    "        for i in range(n+1):\n",
    "            new_target = part_sum[i] + target\n",
    "            l = i+1\n",
    "            r = n\n",
    "            while l < r:\n",
    "                mid = (l+r) // 2\n",
    "                if part_sum[mid] < new_target:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid\n",
    "            if part_sum[r] >= new_target:\n",
    "                out = min(out, r-i)\n",
    "            print(new_target,r,i,r-i)\n",
    "        return out\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        #前缀和+二分\n",
    "        if not len(nums):\n",
    "            return 0\n",
    "        import bisect\n",
    "\n",
    "\n",
    "        sumn = [0, nums[0]]\n",
    "        for x in nums[1:]:\n",
    "            sumn.append(sumn[-1] + x)\n",
    "        if sumn[-1] < target:\n",
    "            return 0\n",
    "        else:\n",
    "            ans = len(nums)\n",
    "        for idx, x in enumerate(sumn):\n",
    "            r = bisect.bisect_left(sumn, x + target)\n",
    "            if r >=  len(sumn):\n",
    "                continue\n",
    "            if ans >= r - idx:\n",
    "                ans = r - idx\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "\n",
    "        ans = []\n",
    "        length = len(nums)\n",
    "        nums_sum = collections.deque()\n",
    "        if sum(nums)<target: return 0\n",
    "        for i in nums:\n",
    "            nums_sum.append(i)\n",
    "            if sum(nums_sum)>=target:\n",
    "                while nums_sum and sum(nums_sum)>=target:\n",
    "                    nums_sum.popleft()\n",
    "                ans.append(len(nums_sum)+1) \n",
    "        if len(ans)<1:return 0\n",
    "        return min(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "\n",
    "        N = len(nums)\n",
    "        S = [0]\n",
    "        total = 0\n",
    "        ans = []\n",
    "        for i in range(N):\n",
    "            total += nums[i]\n",
    "            S.append(total)\n",
    "\n",
    "        if total < target: return 0 \n",
    "        print(S)\n",
    "\n",
    "        # for i in range(0,N+1):\n",
    "        #     for j in range(i+1,N+1):\n",
    "        #         if S[j] - S[i] >= target:\n",
    "        #             ans.append(j-i)\n",
    "        #             break\n",
    "            \n",
    "        for i in range(0,N):\n",
    "            L = i+1\n",
    "            R = N\n",
    "            mid = L + (R-L) //2\n",
    "\n",
    "            while L <= R:\n",
    "                if S[mid] - S[i] >= target and S[mid-1] - S[i] < target:\n",
    "                    ans.append(mid-i)\n",
    "                    break\n",
    "                elif S[mid] - S[i] < target:\n",
    "                    L = mid + 1\n",
    "                else:\n",
    "                    R = mid - 1\n",
    "\n",
    "                mid = L + (R-L) //2\n",
    "            \n",
    "        \n",
    "        print(ans)\n",
    "        n = len(ans)\n",
    "        if n == 0: \n",
    "            return 0\n",
    "        return min(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            sum = 0\n",
    "            for j in range(i, n):\n",
    "                sum += nums[j]\n",
    "                if sum >= target:\n",
    "                    res.append(j-i+1)\n",
    "                    break\n",
    "        if res:\n",
    "            return min(res)\n",
    "        else:\n",
    "            return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "\n",
    "        N = len(nums)\n",
    "        S = [0]\n",
    "        total = 0\n",
    "        ans = []\n",
    "        for i in range(N):\n",
    "            total += nums[i]\n",
    "            S.append(total)\n",
    "            # if total >= target:\n",
    "            #     ans.append(i+1)\n",
    "\n",
    "        if total < target: return 0 \n",
    "        print(S)\n",
    "\n",
    "        for i in range(0,N+1):\n",
    "            for j in range(i+1,N+1):\n",
    "                if S[j] - S[i] >= target:\n",
    "                    ans.append(j-i)\n",
    "                    break\n",
    "            \n",
    "            # left = i + 1\n",
    "            # right = N - 1\n",
    "            # mid = left + (right-left) //2\n",
    "            # while left <= right:\n",
    "            #     if S[N] - S[i] < target:\n",
    "            #         break\n",
    "            #     # if S[mid] - S[i] == target or (S[mid] - S[i] > target and S[mid-1] - S[i] < target):\n",
    "            #     #     ans.append(mid-i+1)\n",
    "            #     #     break\n",
    "            #     # if S[mid] - S[i] > target:\n",
    "            #     #     right = mid - 1\n",
    "            #     # if S[mid] - S[i] < target:\n",
    "            #     #     left = mid + 1\n",
    "                \n",
    "            #     mid = left + (right-left) //2\n",
    "            \n",
    "        \n",
    "        print(ans)\n",
    "        n = len(ans)\n",
    "        if n == 0: \n",
    "            return 0\n",
    "        return min(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        res = []\n",
    "        sums = 0\n",
    "        slow = fast = 0\n",
    "        while fast < len(nums):\n",
    "            sums += nums[fast]\n",
    "            while sums >= target:\n",
    "                res.append(fast - slow + 1)\n",
    "                sums -= nums[slow]\n",
    "                slow += 1\n",
    "            fast += 1\n",
    "        \n",
    "        return min(res) if res else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        #特殊情况\n",
    "        if sum(nums)<target:\n",
    "            return 0\n",
    "\n",
    "        tmp = 0\n",
    "        n = len(nums)\n",
    "        min_length = 0\n",
    "        for i in range(n):\n",
    "            if nums[i]>=target:\n",
    "                return 1\n",
    "            tmp += nums[i]\n",
    "            nums[i] = tmp\n",
    "            if tmp >= target and min_length == 0:\n",
    "                min_length = i+1\n",
    "        #此时nums一定是一个递增数组。要找到nums[j]-nums[i]>=target成立时最小的j-i+1\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if nums[j]-nums[i]>=target:\n",
    "                    min_length = min(min_length,j-i)\n",
    "                    break\n",
    "        print(nums,min_length)\n",
    "        return min_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            s += nums[i]\n",
    "        if s < target:\n",
    "            return 0\n",
    "        res = []\n",
    "        l = 0\n",
    "        a = 0\n",
    "        for i in range(n):\n",
    "            a += nums[i]\n",
    "            if a >= target:\n",
    "                while a >= target:\n",
    "                    res.append(i - l + 1)\n",
    "                    a -= nums[l]\n",
    "                    l += 1\n",
    "        \n",
    "        return min(res) \n",
    "        \n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        if target>sum(nums):\n",
    "            return 0\n",
    "        if target<=min(nums) or target in set(nums):\n",
    "            return 1\n",
    "        a,b=0,1\n",
    "        tsum=nums[a]\n",
    "        l=len(nums)\n",
    "        ans=10**5+1\n",
    "        while a<l and b<l and a<=b:\n",
    "            while b<l and tsum<target:\n",
    "                tsum+=nums[b]\n",
    "                b+=1\n",
    "            while a<l and a<=b and tsum>=target:\n",
    "                ans=min(ans, b-a)\n",
    "                tsum-=nums[a]\n",
    "                a+=1\n",
    "                \n",
    "\n",
    "            # if a+1<b:\n",
    "            #     tsum-=nums[a]\n",
    "            #     a+=1\n",
    "            # print(a,b,tsum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        length  = len(nums)\n",
    "        res = []\n",
    "        i = 0\n",
    "        j = -1\n",
    "        sum = 0\n",
    "        while j<length-1:\n",
    "            if sum < target:\n",
    "                \n",
    "                j+=1\n",
    "                sum+=nums[j]               \n",
    "            else :\n",
    "                \n",
    "                res.append(j-i+1)\n",
    "                sum-=nums[i]\n",
    "                i+=1\n",
    "        while i<=j:\n",
    "            if sum<target:\n",
    "                break\n",
    "            else:    \n",
    "                res.append(j-i+1)\n",
    "                sum-=nums[i]\n",
    "                i+=1\n",
    "        if not res:return 0\n",
    "        return min(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        if sum(nums) < target: \n",
    "            return 0\n",
    "        dp = [9999 for _ in range(len(nums))]\n",
    "        c = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i, len(nums)):\n",
    "                c += nums[j]\n",
    "                if c >= target:\n",
    "                    dp[i] = j-i+1\n",
    "                    break\n",
    "            c = 0\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        res,i,j = [],0,1\n",
    "        while i < len(nums) and j <= len(nums):\n",
    "            j = i+1\n",
    "            while i < j and j <= len(nums):\n",
    "                if sum(nums[i:j])<target:j+=1\n",
    "                elif sum(nums[i:j])>=target:\n",
    "                    res.append(j-i)\n",
    "                    i+=1\n",
    "        return min(res) if len(res) else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        def list_sum(a,b):\n",
    "            summ=[]\n",
    "            for i in range(0,len(a)):\n",
    "                summ.append(a[i]+b[i])\n",
    "            return summ\n",
    "        if sum(nums)<target:\n",
    "            return 0\n",
    "        if max(nums)>=target:\n",
    "            return 1\n",
    "        slide_window=2\n",
    "        summ_list=[]\n",
    "        for i in range(0,len(nums)):\n",
    "            summ_list.append(nums[i])\n",
    "        while slide_window<=len(nums):\n",
    "            summ_list=list_sum(summ_list[0:len(nums)-slide_window+1],nums[slide_window-1:])\n",
    "            if max(summ_list)>=target:\n",
    "                return slide_window\n",
    "            # for i in range(0,len(nums)-slide_window+1):\n",
    "            #     for j in range(i,i+slide_window):\n",
    "            #         summ+=nums[j]\n",
    "            #     if summ>=target:\n",
    "            #         return slide_window\n",
    "            #     summ_list.append()\n",
    "            #     summ=0\n",
    "            slide_window+=1\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        res = []\n",
    "        \n",
    "        left = 0\n",
    "        right = 1\n",
    "        n = len(nums)\n",
    "        while right <= n:\n",
    "            if sum(nums[left:right]) == target:\n",
    "                res.append(right-left)\n",
    "                right += 1\n",
    "                left += 1\n",
    "\n",
    "            elif sum(nums[left:right]) < target:\n",
    "                right += 1\n",
    "            else:\n",
    "                res.append(right-left)  \n",
    "                left += 1\n",
    "        return min(res) if res else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "    #     ''' 先进先出队列实现 '''\n",
    "    #     if sum(nums) < target: return 0\n",
    "    #     queue = []\n",
    "    #     min_len, cur_sum, cur_len = len(nums), 0, 0\n",
    "    #     for value in nums:\n",
    "    #         if value >= target: return 1\n",
    "    #         cur_sum += value\n",
    "    #         cur_len += 1\n",
    "    #         queue.append(value)\n",
    "    #         while cur_sum >= target:\n",
    "    #             if cur_len < min_len:\n",
    "    #                 min_len = cur_len\n",
    "    #             head = queue.pop(0)\n",
    "    #             cur_sum -= head\n",
    "    #             cur_len -= 1\n",
    "    #     return min_len\n",
    "\n",
    "        def minSubArrayLen(self, s: int, nums: List[int]) -> int:\n",
    "            if not nums or sum(nums) < s:\n",
    "                return 0\n",
    "        \n",
    "            n = len(nums)\n",
    "            ans = n + 1\n",
    "            sums = [0]\n",
    "            # 计算各位置的累积和\n",
    "            for i in range(n):\n",
    "                sums.append(sums[-1] + nums[i])\n",
    "            \n",
    "            for i in range(1, n+1):\n",
    "                # 寻找以当前位置i开头的连续子数组，且其和大于等于s\n",
    "                target = s + sums[i-1]\n",
    "                bound = bisect.bisect_left(sums, target)\n",
    "                if bound != len(sums):\n",
    "                    ans = min(ans, bound - (i - 1))\n",
    "            \n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        record = [0]\n",
    "        for i in range(n):\n",
    "            record.append(record[-1] + nums[i])\n",
    "        if record[-1] < target:\n",
    "            return 0\n",
    "        print(record)\n",
    "        res = n\n",
    "        for i in range(n):\n",
    "            left = i+1\n",
    "            right = n\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if record[mid] - record[i] >= target:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            print(record[i], record[left])\n",
    "            if record[left] - record[i] >= target:\n",
    "                res = min(left-i, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        pre_sum = list(accumulate(nums, initial=0))\n",
    "        n = len(pre_sum)\n",
    "        res = inf\n",
    "        left = 0\n",
    "        for right in range(n):\n",
    "            while left <= right and pre_sum[right] - pre_sum[left] >= target:\n",
    "                    res = min(res,right-left)\n",
    "                    left +=1\n",
    "        return  0 if  res == inf else  res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        s = sum(nums)\n",
    "        if target>s:\n",
    "            return 0\n",
    "        if target==s:\n",
    "            return len(nums)\n",
    "        ls,rs = [0 ],[0]\n",
    "        l,r = 0,0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            l += nums[i]\n",
    "            r += nums[-i-1]\n",
    "            ls.append(l)\n",
    "            rs.append(r)\n",
    "        rs = rs[::-1]\n",
    "        l,r = 0,n\n",
    "        ml = n\n",
    "        target = s-target\n",
    "        while r>l and l>=0:\n",
    "            cur = ls[l]+rs[r]\n",
    "            if cur<=target:\n",
    "                ml = min(ml,r-l)\n",
    "                l+=1\n",
    "            else:\n",
    "                l-=1\n",
    "                r-=1\n",
    "        # l,r = 0,n\n",
    "        # while r>l:\n",
    "        #     cur = ls[l]+rs[r]\n",
    "        #     if cur<=target:\n",
    "        #         ml = min(ml,r-l)\n",
    "        #         if cur==target:\n",
    "        #             r-=1\n",
    "        #             l+=1\n",
    "        #         else:\n",
    "        #             r-=1\n",
    "        #     else:\n",
    "        #         r-=1\n",
    "        return  ml\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 滑窗 时间复杂度O(n)\n",
    "    # def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "    #     window_sum = 0\n",
    "    #     n = len(nums)\n",
    "    #     res = math.inf\n",
    "    #     l , r = 0, 0\n",
    "    #     while r < n:\n",
    "    #         window_sum += nums[r]\n",
    "    #         while window_sum >= target:\n",
    "    #             res = min(res, r - l + 1)\n",
    "    #             window_sum -= nums[l]\n",
    "    #             l += 1\n",
    "    #         r += 1\n",
    "    #     return res if res <= len(nums) else 0\n",
    "\n",
    "    # 前缀和 + 二分 时间复杂度O(n log(n))\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = math.inf\n",
    "        pre_sum = [0 for _ in range(n + 1)]\n",
    "        for i in range(0, n):\n",
    "            pre_sum[i + 1] = pre_sum[i] + nums[i]\n",
    "        if pre_sum[-1] < target: return 0\n",
    "        for i in range(n + 1):\n",
    "            l, r = i, n + 1\n",
    "            while l < r:\n",
    "                mid = l + (r - l) // 2\n",
    "                if pre_sum[mid] - pre_sum[i] >= target:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if l < n + 1:\n",
    "                res = min(res, l - i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        ans = float('inf')\n",
    "        sums = [0]\n",
    "        for i in range(len(nums)):\n",
    "            sums.append(sums[-1] + nums[i])\n",
    "        def binary_search(nums: List[int], target: int) -> int:\n",
    "            l = 0\n",
    "            r = len(nums)\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if nums[mid] < target:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid\n",
    "            return l\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            new_target = target + sums[i - 1]\n",
    "            idx = binary_search(sums, new_target)\n",
    "            if idx != len(sums):\n",
    "                ans = min(ans, idx - i + 1)\n",
    "        return 0 if ans == float('inf') else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = n+1\n",
    "        prefixSum = [0]\n",
    "        for i in range(n):\n",
    "            prefixSum.append(prefixSum[-1] + nums[i])\n",
    "        for i in range(1,n+1):\n",
    "            d = prefixSum[i] - target\n",
    "            l = 0\n",
    "            r = i\n",
    "            while(l < r):\n",
    "                mid = l+r+1>>1\n",
    "                if(prefixSum[mid] <= d):\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid-1\n",
    "            if prefixSum[r] <= d:res = min(res, i - r)\n",
    "        return 0 if res == n+1 else res\n",
    "\n",
    "                \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        n = len(nums)\n",
    "        ans = n + 1\n",
    "        sums = [0]\n",
    "        for i in range(n):\n",
    "            sums.append(sums[-1]+nums[i])\n",
    "        \n",
    "        for i in range(1,n+1):\n",
    "            s = target + sums[i-1]\n",
    "            bound = bisect.bisect_left(sums, s)\n",
    "            if bound != len(sums):\n",
    "                ans = min(ans, bound - (i - 1))\n",
    "            \n",
    "        return 0 if ans == n + 1 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s: int, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        n = len(nums)\n",
    "        ans = n + 1\n",
    "        sums = [0]\n",
    "        for i in range(n):\n",
    "            sums.append(sums[-1] + nums[i])\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            target = s + sums[i - 1]\n",
    "            bound = bisect.bisect_left(sums, target)\n",
    "            if bound != len(sums):\n",
    "                ans = min(ans, bound - (i - 1))\n",
    "        \n",
    "        return 0 if ans == n + 1 else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s: int, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        n = len(nums)\n",
    "        ans = n + 1\n",
    "        sums = [0]\n",
    "        for i in range(n):\n",
    "            sums.append(sums[-1] + nums[i])\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            target = s + sums[i - 1]\n",
    "            bound = bisect.bisect_left(sums, target)\n",
    "            if bound != len(sums):\n",
    "                ans = min(ans, bound - (i - 1))\n",
    "        \n",
    "        return 0 if ans == n + 1 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s: int, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        n = len(nums)\n",
    "        ans = n + 1\n",
    "        sums = [0]\n",
    "        for i in range(n):\n",
    "            sums.append(sums[-1] + nums[i])\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            target = s + sums[i - 1]\n",
    "            bound = bisect.bisect_left(sums, target)\n",
    "            if bound != len(sums):\n",
    "                ans = min(ans, bound - (i - 1))\n",
    "        \n",
    "        return 0 if ans == n + 1 else ans\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/2VG8Kg/solutions/1037546/he-da-yu-deng-yu-target-de-zui-duan-zi-s-ixef/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        # 累加数组\n",
    "        addNums = []\n",
    "        total = 0\n",
    "        for num in nums:\n",
    "            if num >= target:\n",
    "                return 1\n",
    "            total += num\n",
    "            addNums.append(total)\n",
    "        \n",
    "        # 正整数数组，没有负数\n",
    "        if total < target:\n",
    "            return 0\n",
    "        elif total == target:\n",
    "            return n\n",
    "        \n",
    "        # 连续子数组包含最后一个数组时\n",
    "        # 二分查找 diff 所在的索引 index\n",
    "        diff = total - target\n",
    "        index = bisect.bisect_right(addNums, diff)\n",
    "        rs = n - index  # 从 index ~ n -1\n",
    "\n",
    "        leftTotal = 0 if index == 0 else addNums[index - 1]\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if addNums[i] < target:\n",
    "                break\n",
    "            while addNums[i] - leftTotal < target:\n",
    "                index -= 1\n",
    "                leftTotal = 0 if index == 0 else addNums[index - 1]\n",
    "            rs = min(rs, i - index + 1)\n",
    "        \n",
    "        return rs\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
